package codeTopPractice;

/**
 * 给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target  ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/binary-search
 */
public class 二分查找 {

    public static void main(String[] args) {

    }

    public static int search(int[] nums,int target){
        return helpSearch(nums,0,nums.length-1,target);
    }

    //递归
    public static int helpSearch(int[] nums,int l,int r,int target){
        //递归过程中出现左指针大于右指针，说明数组中没有target对应的数字
        if(l>r) return -1;
        //数组长度只有1时直接与target做判断
        if(nums.length==1){
            if(nums[l]==target){
                return l;
            }else {
                return -1;
            }
        }
        //取中间指针
        int mid = (l+r)/2;
        //判断target和中间值大小关系，调用对应数组范围递归查找，若相等直接返回mid
        if(target>nums[mid]) return helpSearch(nums,mid+1,r,target);
        if(target<nums[mid]) return helpSearch(nums,l,mid-1,target);
        return mid;
    }

}
